/**
 * 描述：组合问题
 *  从n个东西里去m个：
 *  C(n,m) = C(n-1, m-1) + C(n-1, m)
 *  C(n-1, m-1)表示第n个东西被选了
 *  C(n-1, m)表示第n个东西没有被选
 * @author wangb
 * @version 1.0
 * create 2018-11-05-0:26
 */
public class CombinationProblem{
    private static final int N = 20;
    private static final int M = 10;
    private static int[][] result;
    //开启了无脑模式
    public static int solve(int n, int m) {
        if (n < m) {
            return 0;
        }
        if (m == 0) {
            return 1;
        }

        //记忆化搜索
        if (result[n][m] >= 0) {
            return result[n][m];
        }

        result[n][m] = solve (n - 1, m - 1) + solve (n - 1, m);
        return result[n][m];
    }

    //这个写的好无脑
    public static int solveDitui(int n, int m) {

        //difference between others
        //赋初值不太一样。
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                if (i == j || j == 0) {
                    result[i][j] = 1;
                }
                if (i < j) {
                    result[i][j] = 0;
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                result[i][j] = result[i-1][j-1] + result[i-1][j];
            }
        }

        return result[n][m];
    }

    public static void main(String[] args) {
        result = new int[N+1][M+1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                result[i][j] = -1;
            }
        }
        long start = System.currentTimeMillis();
        System.out.println(solve (N, M));
        System.out.println("Time:" + (System.currentTimeMillis() - start) + " ms");

        long start2 = System.currentTimeMillis();
        System.out.println(solveDitui(N, M));
        System.out.println("Time:" + (System.currentTimeMillis() - start2) + " ms");
    }
}
